public class L701 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        treeNode.right = treeNode2;

        new Solution().insertIntoBST(treeNode, 3);
    }

    static class Solution {

        TreeNode pre;

        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null) {
                return new TreeNode(val);
            }
            helper(root, val, 1);
            return root;
        }

        private void helper(TreeNode root, int val, int flag) {
            if (root == null) {
                TreeNode treeNode = new TreeNode(val);
                if (flag == 1) {
                    pre.left = treeNode;
                } else if (flag == 2) {
                    pre.right = treeNode;
                }
                return;
            }
            pre = root;
            if (root.val > val) {
                helper(root.left, val, 1);
            } else {
                helper(root.right, val, 2);
            }
        }
    }
}
